import common.TreeNode;

import java.util.ArrayList;
import java.util.List;

class BinaryTreeRightSideView {
    /**
     * 方法：通过深度优先搜索实现二叉树的右视图
     * 
     * Args:
     *   root: 二叉树的根节点
     * 
     * Returns:
     *   List<Integer>: 二叉树右侧视图的节点值列表
     * 
     * Time: O(n)，其中 n 是二叉树的节点数，因为每个节点都会被访问一次。
     * Space: O(h)，其中 h 是二叉树的高度，递归栈的空间复杂度与树的高度成正比。
     */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        dfs(root, 0, ans);
        return ans;
    }

    private void dfs(TreeNode node, int depth, List<Integer> ans){
        if(node == null){
            return;
        }
        if(depth == ans.size()){
            ans.add(node.val);
        }
        dfs(node.right, 0, ans);
        dfs(node.left, 0, ans);
    }
}